In subspace clustering, a group of data points belonging to a union ofsubspaces are assigned membership to their respective subspaces. This paperpresents a new approach dubbed Innovation Pursuit (iPursuit) to the problem ofsubspace clustering using a new geometrical idea whereby subspaces areidentified based on their relative novelties. We present two frameworks inwhich the idea of innovation pursuit is used to distinguish the subspaces.Underlying the first framework is an iterative method that finds the subspacesconsecutively by solving a series of simple linear optimization problems, eachsearching for a direction of innovation in the span of the data potentiallyorthogonal to all subspaces except for the one to be identified in one step ofthe algorithm. A detailed mathematical analysis is provided establishingsufficient conditions for iPursuit to correctly cluster the data. The proposedapproach can provably yield exact clustering even when the subspaces havesignificant intersections. It is shown that the complexity of the iterativeapproach scales only linearly in the number of data points and subspaces, andquadratically in the dimension of the subspaces. The second frameworkintegrates iPursuit with spectral clustering to yield a new variant ofspectral-clustering-based algorithms. The numerical simulations with both realand synthetic data demonstrate that iPursuit can often outperform thestate-of-the-art subspace clustering algorithms, more so for subspaces withsignificant intersections, and that it significantly improves thestate-of-the-art result for subspace-segmentation-based face clustering.
展开▼
